πŸ‘©β€πŸ’» 67258. 보석 μ‡Όν•‘

@Seongukbaek Posted April 29, 2022 Β· Updated April 29, 2022 Β· 7 min read

문제

개발자 μΆœμ‹ μœΌλ‘œ 세계 졜고의 κ°‘λΆ€κ°€ 된 μ–΄ν”ΌμΉ˜λŠ” 슀트레슀λ₯Ό 받을 λ•Œλ©΄ 이λ₯Ό ν’€κΈ° μœ„ν•΄ μ˜€ν”„λΌμΈ λ§€μž₯에 쇼핑을 ν•˜λŸ¬ κ°€κ³€ ν•©λ‹ˆλ‹€. μ–΄ν”ΌμΉ˜λŠ” 쇼핑을 ν•  λ•Œλ©΄ λ§€μž₯ μ§„μ—΄λŒ€μ˜ νŠΉμ • λ²”μœ„μ˜ 물건듀을 λͺ¨λ‘ 싹쓸이 κ΅¬λ§€ν•˜λŠ” μŠ΅κ΄€μ΄ μžˆμŠ΅λ‹ˆλ‹€. μ–΄λŠ λ‚  슀트레슀λ₯Ό ν’€κΈ° μœ„ν•΄ 보석 λ§€μž₯에 쇼핑을 ν•˜λŸ¬ κ°„ μ–΄ν”ΌμΉ˜λŠ” μ΄μ „μ²˜λŸΌ μ§„μ—΄λŒ€μ˜ νŠΉμ • λ²”μœ„μ˜ 보석을 λͺ¨λ‘ κ΅¬λ§€ν•˜λ˜ νŠΉλ³„νžˆ μ•„λž˜ λͺ©μ μ„ λ‹¬μ„±ν•˜κ³  μ‹Άμ—ˆμŠ΅λ‹ˆλ‹€. μ§„μ—΄λœ λͺ¨λ“  μ’…λ₯˜μ˜ 보석을 적어도 1개 이상 ν¬ν•¨ν•˜λŠ” κ°€μž₯ 짧은 ꡬ간을 μ°Ύμ•„μ„œ ꡬ맀

예λ₯Ό λ“€μ–΄ μ•„λž˜ μ§„μ—΄λŒ€λŠ” 4μ’…λ₯˜μ˜ 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8κ°œκ°€ μ§„μ—΄λœ μ˜ˆμ‹œμž…λ‹ˆλ‹€.

μ§„μ—΄λŒ€ 번호 1 2 3 4 5 6 7 8
보석 이름 DIA RUBY RUBY DIA DIA EMERALD SAPPHIRE DIA

μ§„μ—΄λŒ€μ˜ 3λ²ˆλΆ€ν„° 7λ²ˆκΉŒμ§€ 5개의 보석을 κ΅¬λ§€ν•˜λ©΄ λͺ¨λ“  μ’…λ₯˜μ˜ 보석을 적어도 ν•˜λ‚˜ 이상씩 ν¬ν•¨ν•˜κ²Œ λ©λ‹ˆλ‹€.

μ§„μ—΄λŒ€μ˜ 3, 4, 6, 7번의 λ³΄μ„λ§Œ κ΅¬λ§€ν•˜λŠ” 것은 쀑간에 νŠΉμ • ꡬ간(5번)이 λΉ μ§€κ²Œ λ˜λ―€λ‘œ μ–΄ν”ΌμΉ˜μ˜ μ‡Όν•‘ μŠ΅κ΄€μ— λ§žμ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

μ§„μ—΄λŒ€ 번호 μˆœμ„œλŒ€λ‘œ λ³΄μ„λ“€μ˜ 이름이 μ €μž₯된 λ°°μ—΄ gemsκ°€ λ§€κ°œλ³€μˆ˜λ‘œ μ£Όμ–΄μ§‘λ‹ˆλ‹€. μ΄λ•Œ λͺ¨λ“  보석을 ν•˜λ‚˜ 이상 ν¬ν•¨ν•˜λŠ” κ°€μž₯ 짧은 ꡬ간을 μ°Ύμ•„μ„œ return ν•˜λ„λ‘ solution ν•¨μˆ˜λ₯Ό μ™„μ„±ν•΄μ£Όμ„Έμš”. κ°€μž₯ 짧은 κ΅¬κ°„μ˜ μ‹œμž‘ μ§„μ—΄λŒ€ λ²ˆν˜Έμ™€ 끝 μ§„μ—΄λŒ€ 번호λ₯Ό μ°¨λ‘€λŒ€λ‘œ 배열에 λ‹΄μ•„μ„œ return ν•˜λ„λ‘ ν•˜λ©°, λ§Œμ•½ κ°€μž₯ 짧은 ꡬ간이 μ—¬λŸ¬ 개라면 μ‹œμž‘ μ§„μ—΄λŒ€ λ²ˆν˜Έκ°€ κ°€μž₯ μž‘μ€ ꡬ간을 return ν•©λ‹ˆλ‹€.

μ œν•œμ‚¬ν•­

  • gems λ°°μ—΄μ˜ ν¬κΈ°λŠ” 1 이상 100,000 μ΄ν•˜μž…λ‹ˆλ‹€.

    • gems λ°°μ—΄μ˜ 각 μ›μ†ŒλŠ” μ§„μ—΄λŒ€μ— λ‚˜μ—΄λœ 보석을 λ‚˜νƒ€λƒ…λ‹ˆλ‹€.
    • gems λ°°μ—΄μ—λŠ” 1번 μ§„μ—΄λŒ€λΆ€ν„° μ§„μ—΄λŒ€ 번호 μˆœμ„œλŒ€λ‘œ 보석이름이 μ°¨λ‘€λŒ€λ‘œ μ €μž₯λ˜μ–΄ μžˆμŠ΅λ‹ˆλ‹€.
    • gems λ°°μ—΄μ˜ 각 μ›μ†ŒλŠ” 길이가 1 이상 10 μ΄ν•˜μΈ μ•ŒνŒŒλ²³ λŒ€λ¬Έμžλ‘œλ§Œ κ΅¬μ„±λœ λ¬Έμžμ—΄μž…λ‹ˆλ‹€.

μž…μΆœλ ₯ 예

gems return
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7]
["AA", "AB", "AC", "AA", "AC"] [1, 3]
["XYZ", "XYZ", "XYZ"] [1, 1]
["ZZZ", "YYY", "NNNN", "YYY", "BBB"] [1, 5]

πŸ“ Logic

while (true) { // 아직 μ’…λ₯˜κ°€ λ‹€ μ•ˆ μ±„μ›Œμ§„ 경우 if (gemTypes != gemMap.size()) { if (right == gems.length) break; else { // 보석을 κ΅¬λ§€ν•˜λŠ” 경우둜, Map에 개수λ₯Ό μ¦κ°€μ‹œν‚€λ©΄μ„œ 보석을 μ €μž₯ gemMap.put(gems[right], gemMap.getOrDefault(gems[right], 0) + 1); right++; } } // μ’…λ₯˜κ°€ λ‹€ μ±„μ›Œμ§„ 경우 if (gemTypes == gemMap.size()) { // μ΄μ „κΉŒμ§€ κ΅¬ν•œ κ΅¬κ°„μ˜ 길이와 λΉ„κ΅ν•˜μ—¬ μž‘λ‹€λ©΄ update if (right - left < distance) { distance = right - left; start = left; end = right; } // ꡬ간 쀄이기 μœ„ν•΄ 제일 μ•ž 보석 1개 μ‚­μ œ gemMap.put(gems[left], gemMap.get(gems[left]) - 1); // 보석 κ°œμˆ˜κ°€ 0개이면 mapμ—μ„œ μ‚­μ œ if (gemMap.get(gems[left]) == 0) gemMap.remove(gems[left]); left++; } }
  • left , right λΌλŠ” 포인터λ₯Ό μ‚¬μš©ν•˜μ—¬ 보석 μ§„μ—΄λŒ€λ₯Ό νƒμƒ‰ν•œλ‹€.
  • 보석 μ§„μ—΄λŒ€μ— 놓인 λͺ¨λ“  μ’…λ₯˜μ˜ 보석을 ν•˜λ‚˜ 이상 κ΅¬λ§€ν•œ κ²½μš°μ™€, κ·Έλ ‡μ§€ μ•Šμ€ 경우둜 λ‚˜λˆˆλ‹€.

    • λ‹€ μ±„μ›Œμ§€μ§€ μ•Šμ€ κ²½μš°λŠ” κ΅¬λ§€ν•œ λ³΄μ„μ˜ 개수 정보λ₯Ό μ—…λ°μ΄νŠΈν•˜λ©΄μ„œ Map 에 μ €μž₯ν•˜κ³ ,
    • λ‹€ μ±„μ›Œμ§„ κ²½μš°λŠ” μ΅œμ†Œ ꡬ간인지 ν™•μΈν•˜κ³  μ‹œμž‘μ λΆ€ν„° 보석 개수λ₯Ό ν•˜λ‚˜μ”© 쀄인닀.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { public int[] solution(String[] gems) { // λ³΄μ„μ˜ μœ„μΉ˜λ₯Ό μ €μž₯ν•  Map Map<String, Integer> gemMap = new HashMap<>(); // μ§„μ—΄λŒ€μ— μžˆλŠ” 보석을 쀑볡 없이 μ €μž₯ν•œ Set Set<String> gemSet = new HashSet<>(Arrays.asList(gems)); // λ³΄μ„μ˜ μ’…λ₯˜λ₯Ό κ΅¬ν•˜κΈ° μœ„ν•΄ Set μ‚¬μš© int gemTypes = gemSet.size(); int distance = Integer.MAX_VALUE; int start = 0, end = 0, left = 0, right = 0; while (true) { // 아직 μ’…λ₯˜κ°€ λ‹€ μ•ˆ μ±„μ›Œμ§„ 경우 if (gemTypes != gemMap.size()) { if (right == gems.length) break; else { // 보석을 κ΅¬λ§€ν•˜λŠ” 경우둜, Map에 개수λ₯Ό μ¦κ°€μ‹œν‚€λ©΄μ„œ 보석을 μ €μž₯ gemMap.put(gems[right], gemMap.getOrDefault(gems[right], 0) + 1); right++; } } // μ’…λ₯˜κ°€ λ‹€ μ±„μ›Œμ§„ 경우 if (gemTypes == gemMap.size()) { // μ΄μ „κΉŒμ§€ κ΅¬ν•œ κ΅¬κ°„μ˜ 길이와 λΉ„κ΅ν•˜μ—¬ μž‘λ‹€λ©΄ update if (right - left < distance) { distance = right - left; start = left; end = right; } // ꡬ간 쀄이기 μœ„ν•΄ 제일 μ•ž 보석 1개 μ‚­μ œ gemMap.put(gems[left], gemMap.get(gems[left]) - 1); // 보석 κ°œμˆ˜κ°€ 0개이면 mapμ—μ„œ μ‚­μ œ if (gemMap.get(gems[left]) == 0) gemMap.remove(gems[left]); left++; } } return new int[] {start + 1, end}; } }

✏️ Review

  • 투 포인터λ₯Ό μ‚¬μš©ν•΄μ•Ό ν•˜λŠ” λ¬Έμ œμž„μ€ λ°”λ‘œ μ•Œ 수 μžˆμ—ˆμ§€λ§Œ, 투 포인터λ₯Ό μ‚¬μš©ν•˜μ§€ μ•Šκ³  각 λ³΄μ„λ“€μ˜ μœ„μΉ˜λ₯Ό μ €μž₯ν•˜κ³  이 μœ„μΉ˜ μ •λ³΄λ§Œμ„ μ‚¬μš©ν•΄μ„œ ν’€ 방법은 μ—†μ„κΉŒλ₯Ό κ³ λ―Όν•΄λ³΄μ•˜λ‹€.
  • 투 포인터 μ•Œκ³ λ¦¬μ¦˜μ„ μ‚¬μš©ν•˜λŠ” κ°€μž₯ ν”ν•œ μ˜ˆκ°€ λΆ€λΆ„ λ°°μ—΄ 합을 κ΅¬ν•˜λŠ” λ¬Έμ œμ˜€λŠ”λ°, 이λ₯Ό 여기에 μ–΄λ–»κ²Œ μ ‘λͺ©μ‹œν‚€λŠ”μ§€ μ˜λ¬Έμ΄μ—ˆλ‹€.
  • 투 포인터 μ•Œκ³ λ¦¬μ¦˜μ΄ κ³ λƒ₯이 λ¬Έμ œμ—λ„ μ‚¬μš©λ˜λ˜λ°, ν•œ 번 혼자 풀어봐야겠닀...

πŸ“• 좜처

Programmers : https://programmers.co.kr/learn/courses/30/lessons/67258

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€